ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpc/rmq/main.cpp

   1 #include <iostream>
   2 #include <vector>
   3 #include <list>
   4 #include <stdlib.h>
   5 #include <utility>
   6 #include <cassert>
   7 #include <sys/types.h>
   8 #include <sys/stat.h>
   9 #include <fcntl.h>
  10 #include <stdio.h>
  11 using namespace std;
  12 #define forit(it,l) for(it=(l).begin();it != (l).end(); it++)
  13 #define forn(i,n) for(unsigned  i= 0; i < ((unsigned)(n)); i++)
  14 #define foreachin(it,s) for(typeof((s).begin()) it = ((s).begin()); it != ((s).end()); it++)
  15 #define forsn(i,s,n) for(int i = (s); i < (n); i++)
  16 void inline llenar_tabla(vector<vector<int> >& tabla, const vector<int>& frec) {
  17     int n = tabla.size();
  18     int i, j;
  19     //init de los intervalos de largo 1
  20     forn(i,n)
  21         tabla[i][0] = i;
  22
  23     //llenado de la tabla desde los mas chicos a los mas grandes
  24         unsigned t=2;
  25         unsigned t_ant=1;
  26     for (j = 1; t <= n; j++) {
  27         for (i = 0; i + (t) - 1 < n; i++) {
  28             int k = j - 1;
  29             if (frec[tabla[i][k]] > frec[tabla[i + (t_ant)][k]])
  30                 tabla[i][j] = tabla[i][k];
  31             else
  32                 tabla[i][j] = tabla[i + (t_ant)][k];
  33         }
  34                 t_ant=t;
  35                 t=t<<1;
  36     }
  37 }
  38
  39
  40 static inline uint32_t log_2(const uint32_t x) {
  41   uint32_t y;
  42   asm ( "\tbsr %1, %0\n"
  43       : "=r"(y)
  44       : "r" (x)
  45   );
  46   return y;
  47 }
  48
  49
  50  void inline cargar_numeros(int cant_numeros,vector<int>& frec,vector<pair<int,int> >& intervalostupla,vector<int>& intervaloindice,int& intervalo) {
  51     int i = 0;
  52     int numero;
  53     int desde,hasta; //intervalo donde todos los elementos son iguales [ ]
  54     int actual; //elemento cuya frecuencia estoy construyendo
  55     while (i < cant_numeros) {
  56         scanf ("%d",&numero);
  57
  58         if (i == 0) {
  59             actual=numero;
  60             desde=0;
  61             hasta=0;
  62         } else {
  63             if (actual==numero) { //si son iguales, incremento el hasta y su frecuencia
  64                 hasta++;
  65                 frec[intervalo]++;
  66             }
  67             // si son distintos, se cerró un intervalo, hay que empezar a armar otro
  68             else {
  69                 intervalostupla[intervalo] = pair<int,int>(desde,hasta);
  70                 intervalo++;
  71                 hasta++;
  72                 desde=hasta;
  73                 actual = numero;
  74             }
  75
  76         }
  77         intervaloindice[i]=intervalo;
  78
  79         i++;
  80
  81     }
  82
  83     //hack: el ultimo siempre quedaba sin agregar
  84     intervalostupla[intervalo] = pair<int,int>(desde,hasta);
  85 }
  86
  87 void inline procesar_queries(const int queries,const vector<int>& frec,const vector<pair<int,int> >& intervalostupla,const vector<int>& intervaloindice,int& intervalo) {
  88     vector<vector<int> > tabla(intervalo+1, vector<int>(log_2(intervalo+1)+1));
  89     llenar_tabla(tabla,frec);
  90     unsigned x,y;
  91     int i=0;
  92     while (i < queries) {
  93         scanf("%u %u",&x,&y);
  94         int desde, hasta;
  95         //desde y hasta son los intervalos extremos que hay que mirar.
  96         //No necesariamente estan completos
  97         desde = intervaloindice[x-1];
  98         hasta = intervaloindice[y-1];
  99
 100         int res;
 101         // Si esos indices son parte del mismo intervalo, la frecuencia es la distancia entre ellos.
 102         if (desde==hasta) {
 103             res = y-x+1;
 104         } else {
 105             //calculo por separado los intervalos que pueden ser truncos
 106             int frec_i = intervalostupla[desde].second - x + 2;
 107             int frec_j = y - intervalostupla[hasta].first ;
 108
 109             //el siguiente del desde y el anterior del hasta si estan completos
 110             unsigned int intervalo_completo_i = desde+1;
 111             unsigned int intervalo_completo_j = hasta-1;
 112
 113             res = max(frec_i,frec_j);
 114             if(intervalo_completo_i <= intervalo_completo_j){
 115                 unsigned int k = log_2(intervalo_completo_j - intervalo_completo_i + 1);
 116                 int aux = frec[tabla[intervalo_completo_j-(1<<k)+1][k]];
 117                 if (frec[tabla[intervalo_completo_i][k]] >= aux )
 118                     res = max(res,frec[tabla[intervalo_completo_i][k]]);
 119                 else
 120                    res = max(res,aux);
 121             }
 122         }
 123
 124         printf("%d\n",res);
 125         i++;
 126     }
 127 }
 128
 129 int main(int argc, char** argv) {
 130 #ifndef ONLINE_JUDGE
 131     close (0);
 132     open ("test.txt", O_RDONLY);
 133     //close (1);
 134     //open ("myprog.out", O_WRONLY | O_CREAT, 0600);
 135 #endif
 136
 137     int cant_numeros,queries;
 138         scanf ("%d",&cant_numeros);
 139
 140
 141     while (cant_numeros > 0) {
 142                 scanf ("%d",&queries);
 143         vector<int> frec(cant_numeros,1);//vector de frecuencias
 144         int intervalo =0;//cantidad de intervalos
 145         vector<int> intervaloindice(cant_numeros); //dado un indice del arreglo, devuelve el numero de intervalo en el que esta
 146         vector<pair<int,int> > intervalostupla(cant_numeros); //dado un numero de intervalo, da su desde y hasta
 147
 148         cargar_numeros(cant_numeros,frec,intervalostupla, intervaloindice, intervalo);
 149         procesar_queries(queries, frec,intervalostupla, intervaloindice, intervalo);
 150
 151
 152         scanf ("%d",&cant_numeros);
 153
 154     }
 155     return (EXIT_SUCCESS);
 156 }
 157
 158